package com.yun.algorithmproblem.leetcode;

public class Leetcode732 {
    //自己的写的方法
    static class MyCalendarThree1 {

        static class Node {
            Node next;
            int startTime;
            int endTime;
            int k;

            public Node() {
            }

            public Node(int startTime, int endTime, int k) {
                this.startTime = startTime;
                this.endTime = endTime;
                this.k = k;
            }

            @Override
            public String toString() {
                return "Node{" +
                        "startTime=" + startTime +
                        ", endTime=" + endTime +
                        ", k=" + k +
                        '}';
            }
        }

        Node head;

        int res = 1;

        private void printNode(Node head) {
            Node p = head;
            int count = 1;
            while (p.next != null) {
                Node q = p.next;
                System.out.print("[" + q.startTime + "," + q.endTime + "," + q.k + "]->");
                count++;
                p = q;
            }
            System.out.println();
        }

        public MyCalendarThree1() {
            head = new Node(-1, -1, -1);
        }

        public int book(int startTime, int endTime) {
            if (head.next == null) {
                head.next = new Node(startTime, endTime, 1);
                return 1;
            }
            Node p = head;
            Node q = p.next;
            while (q != null) {
                if (q.endTime <= startTime) {
                    p = q;
                    q = p.next;
                } else {
                    break;
                }
            }
            addNode(p, q, startTime, endTime);
            System.out.println(startTime + "," + endTime);
            System.out.println(res);
            printNode(head);
            return res;
        }

        private void addNode(Node p, Node q, int startTime, int endTime) {
            if (q == null) {
                p.next = new Node(startTime, endTime, 1);
            } else {
                if (startTime < q.startTime) {
                    if (endTime <= q.startTime) {
                        Node node = new Node(startTime, endTime, 1);
                        p.next = node;
                        node.next = q;
                    } else if (endTime < q.endTime) {
                        Node node1 = new Node(startTime, q.startTime, 1);
                        Node node2 = new Node(q.startTime, endTime, q.k + 1);
                        res = Math.max(res, node2.k);
                        Node node3 = new Node(endTime, q.endTime, q.k);
                        p.next = node1;
                        node1.next = node2;
                        node2.next = node3;
                        node3.next = q.next;
                        q.next = null;
                    } else {
                        Node node = new Node(startTime, q.startTime, 1);
                        q.k++;
                        res = Math.max(res, q.k);
                        p.next = node;
                        node.next = q;
                        if (endTime > q.endTime) {
                            addNode(q, q.next, q.endTime, endTime);
                        }
                    }
                } else if (startTime == q.startTime) {
                    if (endTime < q.endTime) {
                        Node node1 = new Node(startTime, endTime, q.k + 1);
                        res = Math.max(res, node1.k);
                        Node node2 = new Node(endTime, q.endTime, q.k);
                        p.next = node1;
                        node1.next = node2;
                        node2.next = q.next;
                        q.next = null;
                    } else {
                        q.k++;
                        res = Math.max(res, q.k);
                        if (endTime > q.endTime) {
                            addNode(q, q.next, q.endTime, endTime);
                        }
                    }
                } else {
                    if (endTime < q.endTime) {
                        Node node1 = new Node(q.startTime, startTime, q.k);
                        Node node2 = new Node(startTime, endTime, q.k + 1);
                        res = Math.max(res, node2.k);
                        Node node3 = new Node(endTime, q.endTime, q.k);
                        p.next = node1;
                        node1.next = node2;
                        node2.next = node3;
                        node3.next = q.next;
                        q.next = null;
                    } else {
                        Node node1 = new Node(q.startTime, startTime, q.k);
                        Node node2 = new Node(startTime, q.endTime, q.k + 1);
                        res = Math.max(res, node2.k);
                        p.next = node1;
                        node1.next = node2;
                        node2.next = q.next;
                        q.next = null;
                        if (endTime > q.endTime) {
                            addNode(node2, node2.next, node2.endTime, endTime);
                        }
                    }
                }
            }
        }
    }

    //线段树
    static class MyCalendarThree {

        int ans;
        public MyCalendarThree() {
            ans=0;
        }

        public int book(int startTime, int endTime) {
            update(root, 0, N, startTime, endTime - 1, 1);
            ans=Math.max(ans,query(root, 0, N, startTime, endTime - 1));
            return ans;
        }

        /**
         * 线段树模板
         */
        class Node {
            Node left, right;
            int val, add;
        }

        private final int N = (int) 1e9;
        private Node root = new Node();

        public void update(Node node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                node.val += val;
                node.add += val;
                return;
            }
            int mid = (start + end) >> 1;
            pushDown(node);
            if (l <= mid) {
                update(node.left, start, mid, l, r, val);
            }
            if (r > mid) {
                update(node.right, mid + 1, end, l, r, val);
            }
            pushUp(node);
        }

        public int query(Node node, int start, int end, int l, int r) {
            if (l <= start && end <= r) {
                return node.val;
            }
            int mid = (start + end) >> 1, ans = 0;
            pushDown(node);
            if (l <= mid) {
                ans = query(node.left, start, mid, l, r);
            }
            if (r > mid) {
                ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
            }
            return ans;
        }

        private void pushUp(Node node) {
            node.val = Math.max(node.left.val, node.right.val);
        }

        private void pushDown(Node node) {
            if (node.left == null) {
                node.left = new Node();
            }
            if (node.right == null) {
                node.right = new Node();
            }
            if (node.add == 0) {
                return;
            }
            node.left.val += node.add;
            node.right.val += node.add;
            node.left.add += node.add;
            node.right.add += node.add;
            node.add = 0;
        }
    }

    public static void main(String[] args) {
        MyCalendarThree obj = new MyCalendarThree();
        obj.book(26, 35);
        obj.book(26, 32);
        obj.book(25, 32);
        obj.book(18, 26);
        obj.book(40, 45);
        obj.book(19, 26);
        obj.book(48, 50);
        obj.book(1, 6);
        obj.book(46, 50);
        obj.book(11, 18);

    }
}
